#include "gx_tree.h"
#include "gx_err.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

void roll_right(TREE_NODE **node)
{
	if (node == NULL|| *node == NULL || (*node)->left == NULL)
		return ;
	else
	{
		TREE_NODE *tmp = *node;
		(*node) = tmp->left;
		tmp->left = (*node)->right;
		(*node)->right = tmp;
	}
}

void roll_left(TREE_NODE **node)
{
	if(node == NULL || *node == NULL||(*node)->right == NULL)
		return ;
	else
	{
		TREE_NODE *tmp = *node;
		(*node) = tmp->right;
		tmp->right = (*node)->left;
		(*node)->left = tmp;
	}
}

RB_TREE_NODE* rb_roll_right(RB_TREE_NODE *node)
{
	if (node == NULL || (node)->left == NULL)
		return NULL;
	else
	{
		RB_TREE_NODE* x = node->left;
		node->left = x->right;
		x->right = node;
		x->parent = node->parent;
		node->parent = x;

		if(node->left != NULL)
			node->left->parent = node;

		return x;
	}
}

RB_TREE_NODE* rb_roll_left(RB_TREE_NODE *node)
{
	if(node == NULL || node->right == NULL)
		return NULL;
	else
	{
		RB_TREE_NODE * x;
		x = node->right;
		node->right = x->left;
		x->left = node;
		x->parent = node->parent;
		node->parent=x;

		if(node->right != NULL)
			node->right->parent = node;

		return x;
	}
}



void roll_min_up(TREE_NODE **node)
{
	if(node == NULL|| *node == NULL)
		return ;
	if((*node)->left != NULL)
	{
		roll_min_up(&((*node)->left));
		roll_right(node);
	}
}


TREE* tree_new(unsigned keysize,unsigned datasize,int (*compare)(const void *d1,const void *d2))
{
	if(compare == NULL && keysize != 0)
		return NULL;

	TREE *t = (TREE*)malloc(sizeof(TREE));

	if(t == NULL)
		return NULL;

	t->tree_link = NULL;
	t->keysize = keysize;
	t->datasize = datasize;
	t->count = 0;

	if(keysize == 0 && compare == NULL)
		t->compare=(int (*)(const void*,const void*))strcmp;
	else
		t->compare = compare;
	return t;
}

static inline void* my_alloc(unsigned size)
{
	void *tmp;
	tmp = malloc(size);
	if(tmp == NULL)
	{
		fatal(NOMEM,"NO MEMORY!\n");
	}
	memset(tmp,0,size);
	return tmp;
}

static TREE_NODE* new_node(void* key,void* data,unsigned keysize,unsigned datasize)
{
	TREE_NODE *node = (TREE_NODE*)my_alloc(sizeof(TREE_NODE));
	unsigned dat_len = 0;
	unsigned key_len = 0;

	if(keysize == 0)
	{
		key_len = strlen((char*)key)+1;
		node->key = my_alloc(key_len*sizeof(char));
		strncpy((char*)node->key,(char*)key,key_len*sizeof(char));

	}
	else
	{
		node->key = my_alloc(keysize);
		memcpy(node->key,key,keysize);
	}

	if(datasize == 0)
	{
		dat_len = strlen((char*)data)+1;
		node->data = my_alloc(dat_len*sizeof(char));
		strncpy((char*)node->data,(char*)data,dat_len*sizeof(char));
	}
	else
	{
		node->data = my_alloc(datasize);
		memcpy(node->data,data,datasize);
	}
	node->left = NULL;
	node->right = NULL;
	return node;
}


static void insert_node(TREE_NODE **node,void* key,void* data,unsigned keysize,unsigned datasize,int* errcode,int (*compare)(const void *d1,const void *d2))
{
	if(node == NULL)
	{
		*errcode = PARAMETER_ERROR;
		return ;
	}
	if(*node == NULL)
	{
		*node = new_node(key,data,keysize,datasize);
		*errcode = SUCCESS;
		return ;
	}

	if(compare((*node)->key,key) == 0)
	{
		*errcode =DATA_EXIT; 
		return;
	}
	else if(compare((*node)->key,key) < 0)
		insert_node(&((*node)->right),key,data,keysize,datasize,errcode,compare);
	else
		insert_node(&((*node)->left),key,data,keysize,datasize,errcode,compare);
}

int tree_add(TREE *t,void *key,void *data)
{
	int errcode = 0;
	if(t == NULL || key == NULL || data == NULL)
		return PARAMETER_ERROR;
	else
	{
		insert_node(&(t->tree_link),key,data,t->keysize,t->datasize,&errcode,t->compare);
		if(errcode == SUCCESS)
			t->count++;
		return errcode;
	}
}

static void insert_node_root(TREE_NODE **node,void* key,void* data,unsigned keysize,unsigned datasize,int* errcode,int (*compare)(const void *d1,const void *d2))
{
	if(node == NULL)
	{
		*errcode = PARAMETER_ERROR;
		return ;
	}

	if(*node == NULL)
	{
		*node = new_node(key,data,keysize,datasize);
		*errcode = SUCCESS;
		return ;
	}

	if(compare((*node)->key,key) == 0)
	{
		*errcode =DATA_EXIT; 
		return;
	}
	else if(compare((*node)->key,key) < 0)
	{
		insert_node_root(&((*node)->right),key,data,keysize,datasize,errcode,compare);
		roll_left(node);
	}
	else
	{
		insert_node_root(&((*node)->left),key,data,keysize,datasize,errcode,compare);
		roll_right(node);
	}
}

int tree_add_root(TREE *t,void *key,void *data)
{
	int errcode = 0;

	if(t == NULL || key == NULL || data == NULL)
		return PARAMETER_ERROR;
	else
	{
		insert_node_root(&(t->tree_link),key,data,t->keysize,t->datasize,&errcode,t->compare);
		if(errcode == SUCCESS)
			t->count++;
		return errcode;

	}
}

void static tree_splay(TREE_NODE **node,void* key,void* data,unsigned keysize,unsigned datasize,int* errcode,int (*compare)(const void *d1,const void *d2))
{
	if(node == NULL)
	{
		*errcode = PARAMETER_ERROR;
		return ;
	}

	if(*node == NULL)
	{
		*node = new_node(key,data,keysize,datasize);
		*errcode = SUCCESS;
		return ;
	}

	if(compare(key,(*node)->key) == 0)
	{
		*errcode = DATA_EXIT;
		return ;
	}
	else if(compare(key,(*node)->key) < 0)
	{
		if((*node)->left == NULL)
		{
			(*node)->left = new_node(key,data,keysize,datasize);
			*errcode = SUCCESS;
			roll_right(node);
			return ;
		}

		if(compare(key,(*node)->left->key) == 0)
		{
			*errcode = DATA_EXIT;
			return;
		}
		else if(compare(key,(*node)->left->key)<0)
		{
			tree_splay(&((*node)->left->left),key,data,keysize,datasize,errcode,compare);
			if(*errcode == SUCCESS)
				roll_right(node);
			else
				return ;
		}
		else
		{
			tree_splay(&((*node)->left->right),key,data,keysize,datasize,errcode,compare);

			if(*errcode == SUCCESS)
				roll_left(&((*node)->left));
			else
				return ;
		}

		roll_right(node);
		return ;
	}
	else
	{
		if((*node)->right == NULL)
		{
			(*node)->right = new_node(key,data,keysize,datasize);
			*errcode = SUCCESS;
			roll_left(node);
			return ;
		}

		if(compare(key,(*node)->right->key) == 0)
		{
			*errcode = DATA_EXIT;
			return ;
		}
		else if(compare(key,(*node)->right->key)<0)
		{
			tree_splay(&((*node)->right->left),key,data,keysize,datasize,errcode,compare);

			if(*errcode == SUCCESS)
				roll_right(&((*node)->right));
			else
				return ;
		}
		else
		{
			tree_splay(&((*node)->right->right),key,data,keysize,datasize,errcode,compare);
			if(*errcode == SUCCESS)
				roll_left(node);
			else
				return;
		}
		roll_left(node);
	}
}

int tree_add_spay(TREE *t,void *key,void *data)
{
	int errcode = 0;

	if(t == NULL || key == NULL || data == NULL)
		return PARAMETER_ERROR;
	else
	{
		tree_splay(&(t->tree_link),key,data,t->keysize,t->datasize,&errcode,t->compare);
		if(errcode == SUCCESS)
			t->count++;
		return errcode;

	}
}

void static remove_all_node(TREE_NODE **node)
{
	if((*node) == NULL)
		return ;

	if((*node)->left != NULL)
	{
		remove_all_node(&((*node)->left));
		(*node)->left = NULL;
	}

	if((*node)->right != NULL)
	{
		remove_all_node(&((*node)->right));
		(*node)->right = NULL;
	}

	if((*node)->key != NULL)
	{
		free((*node)->key);
		(*node)->key=NULL;
	}

	if((*node)->data != NULL)
	{
		free((*node)->data);
		(*node)->data = NULL;
	}

	free((*node));
	*node = NULL;
}

void tree_delete(TREE *t)
{
	if(t == NULL)
		return ;
	else
	{
		remove_all_node(&(t->tree_link));
		free(t);
	}
}

void * search_node(TREE_NODE* node,void *key,int (*compare)(const void * d1,const void *d2))
{
	if(node == NULL)
		return NULL;

	if(compare(node->key,key) == 0)
		return node->data;
	else if(compare(node->key,key) < 0)
		return search_node(node->right,key,compare);
	else
		return search_node(node->left,key,compare);
}

void* tree_search(TREE *t,void *key)
{
	if(t == NULL || key == NULL)
		return NULL;
	return search_node(t->tree_link,key,t->compare);
}

void tree_remove_node(TREE_NODE **node,void *key,int (*compare)(const void *d1,const void *d2),int *errorcode)
{
	if(*node == NULL)
	{
		*errorcode = NODATA;
		return ;
	}
	int result = compare((*node)->key,key);

	if(result < 0)
		tree_remove_node(&((*node)->right),key,compare,errorcode);
	else if(result>0)
		tree_remove_node(&((*node)->left),key,compare,errorcode);
	else
	{
		TREE_NODE *tmp = *node;
		roll_min_up(&((*node)->right));
		if((*node)->right != NULL)
		{
			(*node)->right->left = (*node)->left;
			*node = (*node)->right;
		}
		else
		{
			*node = (*node)->left;
		}
		if(tmp->key != NULL)
			free(tmp->key);
		if(tmp->data != NULL)
			free(tmp->data);
		free(tmp);
		*errorcode = SUCCESS;
	}
}


int tree_remove(TREE * tree,void *key)
{
	int errorcode =0;
	tree_remove_node(&(tree->tree_link),key,tree->compare,&errorcode);
	if(errorcode == SUCCESS)
		tree->count--;
	return errorcode;
}


RB_TREE* rb_tree_new(unsigned keysize,int datasize,int (*compare)(const void *d1,const void *d2),void (*free_data)(void *data))
{
	if(compare == NULL && keysize != 0)
		return NULL;

	RB_TREE *t = (RB_TREE*)my_alloc(sizeof(RB_TREE));

	if(t == NULL)
		return NULL;

	t->tree_link = NULL;
	t->keysize = keysize;
	t->datasize = datasize;
	t->count = 0;
	t->free_data = free_data;

	if(keysize == 0 && compare == NULL)
		t->compare=(int (*)(const void*,const void*))strcmp;
	else
		t->compare = compare;
	return t;
}

static RB_TREE_NODE* new_rb_node(void *key,void *data,unsigned keysize,int datasize,char color)
{
	RB_TREE_NODE *node = (RB_TREE_NODE*)my_alloc(sizeof(RB_TREE_NODE));

	unsigned dat_len = 0;
	unsigned key_len = 0;

	if(keysize == 0)
	{
		key_len = strlen((char*)key)+1;
		node->key = my_alloc(key_len*sizeof(char));
		strncpy((char*)node->key,(char*)key,key_len*sizeof(char));

	}
	else
	{
		node->key = my_alloc(keysize);
		memcpy(node->key,key,keysize);
	}

	if(datasize == 0)
	{
		dat_len = strlen((char*)data)+1;
		node->data = my_alloc(dat_len*sizeof(char));
		strncpy((char*)node->data,(char*)data,dat_len*sizeof(char));
	}
	else if(datasize>0)
	{
		node->data = my_alloc(datasize);
		memcpy(node->data,data,datasize);
	}
	else
	{
		node->data = data;
	}

	node->left = NULL;
	node->right = NULL;
	node->parent = NULL;
	node->color = color;
	return node;
}


static RB_TREE_NODE* insert_rb_node(RB_TREE_NODE **node,void* key,void* data,unsigned keysize,int datasize,int* errcode,int (*compare)(const void *d1,const void *d2),RB_TREE_NODE *parent)
{
	if(node == NULL)
	{
		*errcode = PARAMETER_ERROR;
		return NULL;
	}

	if(*node == NULL)
	{
		*node = new_rb_node(key,data,keysize,datasize,RED);
		*errcode = SUCCESS;
		(*node)->parent = parent;
		return (*node);
	}

	if(compare((*node)->key,key) == 0)
	{
		*errcode =DATA_EXIT; 
		return NULL;
	}
	else if(compare((*node)->key,key) < 0)
		return insert_rb_node(&((*node)->right),key,data,keysize,datasize,errcode,compare,*node);
	else
		return insert_rb_node(&((*node)->left),key,data,keysize,datasize,errcode,compare,*node);
}

static RB_TREE_NODE* rb_insert_rebalance(RB_TREE_NODE *node,RB_TREE_NODE *root)
{
	RB_TREE_NODE *parent;
	RB_TREE_NODE *gparent;
	RB_TREE_NODE *uncle;

	while((parent = node->parent) && (parent->color == RED))
	{
		gparent = parent->parent;

		if(parent == gparent->left)
		{
			uncle = gparent->right;

			if(uncle && uncle->color == RED)
			{
				uncle->color = BLACK;
				parent->color = BLACK;
				gparent->color = RED;
				node = gparent;
			}
			else
			{
				if(parent->right == node)
				{
					gparent->left=rb_roll_left(parent);
					node=gparent->left->left;
					parent = node->parent;
					gparent = node->parent->parent;
				}
				parent->color = BLACK;
				gparent->color = RED;

				if(gparent == root)
					root = rb_roll_right(gparent);
				else
				{
					if(gparent == gparent->parent->right)
						gparent->parent->right = rb_roll_right(gparent);
					else
						gparent->parent->left = rb_roll_right(gparent);

				}
			}
		}
		else
		{
			uncle = gparent->left;
			if(uncle && uncle->color == RED)
			{
				uncle->color = BLACK;
				parent->color = BLACK;
				gparent->color = RED;
				node = gparent;
			}
			else
			{
				if(parent->left == node)
				{
					gparent->right = rb_roll_right(node->parent);
					node= gparent->right->right;
					parent = node->parent;
					gparent = node->parent->parent;
				}
				parent->color = BLACK;
				gparent->color = RED;
				if(gparent == root)
					root = rb_roll_left(parent);
				else
				{
					if(gparent == gparent->parent->right)
						gparent->parent->right = rb_roll_left(gparent);
					else
						gparent->parent->left = rb_roll_left(gparent);
				}
			}
		}
	}
	root->color = BLACK;
	return root;
}

int rb_tree_add(RB_TREE *t,void *key,void *data)
{
	RB_TREE_NODE *rb_node = NULL;
	int errcode=0;
	if(t==NULL || key == NULL || data == NULL)
	{
		return PARAMETER_ERROR;
	}

	if(t->tree_link == NULL)
	{
		t->tree_link = new_rb_node(key,data,t->keysize,t->datasize,BLACK);
		t->count++;
		return SUCCESS;
	}
	else
	{
		rb_node = insert_rb_node(&(t->tree_link),key,data,t->keysize,t->datasize,&errcode,t->compare,t->tree_link);

		if(rb_node == NULL)
			return errcode;
		else
		{
			t->tree_link = rb_insert_rebalance(rb_node,t->tree_link);	
			t->count++;
			return SUCCESS;
		}
	}
}

void static remove_all_rb_node(RB_TREE_NODE **node,int datasize,void(*free_data)(void* data))
{
	if((*node) == NULL)
		return ;

	if((*node)->left != NULL)
	{
		remove_all_rb_node(&((*node)->left),datasize,free_data);
		(*node)->left = NULL;
	}

	if((*node)->right != NULL)
	{
		remove_all_rb_node(&((*node)->right),datasize,free_data);
		(*node)->right = NULL;
	}

	if((*node)->key != NULL)
	{
		free((*node)->key);
		(*node)->key=NULL;
	}

	if((*node)->data != NULL)
	{
		if(datasize >= 0 )
			free((*node)->data);
		else
		{
			if(free_data != NULL)
				free_data((*node)->data);
		}
		(*node)->data = NULL;
	}

	free((*node));
	*node = NULL;
}

void rb_tree_delete(RB_TREE *t)
{
	if(t == NULL)
		return ;
	else
	{
		remove_all_rb_node(&(t->tree_link),t->datasize,t->free_data);
		free(t);
	}
}



static RB_TREE_NODE* rb_tree_remove_node(RB_TREE_NODE *node,void *key,int (*compare)(const void *d1,const void *d2),RB_TREE_NODE *root,int datasize,void(*free_data)(void* data),int *errcode)
{
	if(node == NULL)
	{
		return NULL;
		*errcode = DATA_EXIT;
	}
	int result = compare(node->key,key);

	if(result < 0)
		return rb_tree_remove_node(node->right,key,compare,root,datasize,free_data,errcode);
	else if(result>0)
		return rb_tree_remove_node(node->left,key,compare,root,datasize,free_data,errcode);
	else
	{
		RB_TREE_NODE *old = node;
		RB_TREE_NODE *left=NULL;
		RB_TREE_NODE *child = NULL;
		RB_TREE_NODE *parent = NULL;

		if(old->left && old->right)
		{
			node = old->right;

			while((left = node->left) != NULL)
			{
				node = node->left;
			}

			child = node->right;
			parent = node->parent;

			if(node->parent != old)
			{
				if(child)
				{
					child->parent = parent;
				}

				if(parent->left == node)
				{
					parent->left = child;
				}
				else
				{
					parent->right = child;
				}
				node->right = old->right;
				old->right->parent = node;
			}
			node->parent = old->parent;
			node->color = old->color;
			node->left = old->left;
			old->left->parent = node;
				if(old->parent)
				{
					if(old->parent->left == old)
					{
						old->parent->left = node;
					}
					else
					{
						old->parent->right = node;
					}
				}
				else
				{
					root = node;
				}

		}
		else
		{
			if(old->left == NULL)
			{
				child = node->right;
			}
			else if(old->right == NULL)
			{
				child = node->left;
			}
			else
			{
				child = NULL;
			}
			parent = node->parent;

			if(child)
			{
				child->parent = parent;
				child->color = old->color;
			}

			if(parent)
			{
				if(parent->left == node)
				{
					parent->left = child;
				}
				else
				{
					parent->right = child;
				}
			}
			else
			{
				root = child;
			}
		}

		if( old->key != NULL )
		{
			free(old->key);
			old->key=NULL;
		}

		if(old->data != NULL)
		{
			if(datasize >= 0 )
				free(old->data);
			else
			{
				if(free_data != NULL)
					free_data(old->data);
			}
			old->data = NULL;
		}

		free(old);
		old = NULL;

		*errcode = SUCCESS;
		return root;
	}
}

int rb_tree_remove(RB_TREE *t,void *key)
{
	int errcode =0;
	RB_TREE_NODE* tmp_root = NULL;
	tmp_root = rb_tree_remove_node(t->tree_link,key,t->compare,t->tree_link,t->datasize,t->free_data,&errcode);
	if(errcode == SUCCESS)
		t->tree_link = tmp_root;
	return errcode;
}
